package com.algorithm.tsp;

import java.util.ArrayList;
import java.util.Iterator;
import com.algorithm.basic.BasicMoead;
import com.problem.tsp.TSPProblem;
import com.util.solution.impl.TSPSolution;

public class M2M extends BasicMoead{
	private TSPProblem problem;
	private int run_num;

	public M2M(TSPProblem problem, int type, int run_num){
		super(problem.obj_num, type);
		this.problem = problem;
		this.run_num = run_num;
		weights = new double[problem.sub_num*problem.obj_num];
		boolean ret = initialWeights(problem.sub_num, 0);
		this.problem.initialPopulation3(problem.sub_num, weights);
		if(!ret) System.exit(0);
		this.bind(this.problem);
	}

	public void initialIdealPoint(){
		for(int i=0;i<problem.sub_num;i++){
			int [] values = problem.solutionArray[i].object_val;
			this.udpateIdealPoint(values);
		}
	}
	public void execute(int iteration){
		long startMili=System.currentTimeMillis();
		for(int i = 0;i<iteration;i++){
			System.out.println("iteration of : "+(i+1));
			this.executeMoead();
		}
		long endMili=System.currentTimeMillis();
		System.out.println((endMili-startMili)/1000+" s ");
		String fileName;
		fileName = "F:/m2m/"+problem.problem_des+problem.city_num+"_tch_"+run_num+".txt";
		problem.saveResults(fileName);
	}
	
	public void executeMoead(){
		for(int i=0;i<problem.sub_num;i++){
			TSPSolution curSolution = problem.solutionArray[i];
			if(curSolution.route!=null && curSolution.isSearched()==false){
				problem.solutionArray[i].setSearched(true);
				try {
					TSPSolution s = curSolution.clone();
					this.generateNeighborhood(s);
				} catch (CloneNotSupportedException e) {
					e.printStackTrace();
				}
			}
		}
	}
	/**
	 * generate the neighborhood of s
	 * @param s
	 */
	public void generateNeighborhood(TSPSolution s){
		int [] rounte = new int[problem.city_num+1];
		for(int i=0;i<problem.city_num;i++) rounte[i] = s.route[i];
		rounte[problem.city_num] = rounte[0];
		int [] pos = new int[problem.city_num];
		problem.calculatePosition(rounte, pos);
		int pos1 = 0;
		int pos2 = 0;
		for(int k=0;k<problem.city_num;k++){
			int i = k;
			pos1 = i;
			int curIndex = rounte[i];
			int nextIndex = rounte[i+1];
			ArrayList<Integer> candidate = problem.candidateList.get(curIndex);
			Iterator<Integer> iter = candidate.iterator();
			while(iter.hasNext()){
				int next = iter.next();
				pos2 = pos[next];
				int curIndex1 = rounte[pos2];
				int nextIndex1 = rounte[pos2+1];
				if(curIndex == nextIndex1) continue;
				if(curIndex == curIndex1) continue;
				if(nextIndex == nextIndex1) continue;
				if(curIndex1 == nextIndex) continue;
				int betterTimes = 0;
				TSPSolution solution = new TSPSolution(problem.city_num, problem.obj_num, -1);
				for(int j=0;j<problem.obj_num;j++){
					int gain = problem.disMatrix[j*problem.city_num*problem.city_num+curIndex*problem.city_num+curIndex1] +
							problem.disMatrix[j*problem.city_num*problem.city_num+nextIndex*problem.city_num+nextIndex1] - 
							(problem.disMatrix[j*problem.city_num*problem.city_num+curIndex*problem.city_num+nextIndex]+
							problem.disMatrix[j*problem.city_num*problem.city_num+curIndex1*problem.city_num+nextIndex1]);
					if(gain<0) betterTimes++;
					solution.object_val[j] = s.object_val[j] + gain;
				}
				if(betterTimes==0) continue;
				solution.route = s.route.clone();
				solution.index = s.index;
				problem.converse(pos1, pos2, solution.route, 0);
				this.udpateSubSolutions(solution);
			}
		}
	}
	public boolean udpateSubSolutions(TSPSolution s){
		int index = this.problem.getIndex(s, this.problem.sub_num, weights);
		this.udpateIdealPoint(s.object_val);
		boolean ret = false;
		TSPSolution curSolution = problem.solutionArray[index];
		if(curSolution.route==null) {
			curSolution.object_val = s.object_val.clone();
			curSolution.route = s.route.clone();
			curSolution.setSearched(false);
			ret = true;
		}else {
			double fitness = 0;
			curSolution.fitness = getTchValue(index, curSolution.object_val);
			fitness = getTchValue(index, s.object_val);
			if(curSolution.fitness>fitness){
				curSolution.object_val = s.object_val.clone();
				curSolution.route = s.route.clone();
				curSolution.setSearched(false);
				ret = true;
			}
		}
		return ret;
	}
	public static void main(String[]args){
		for(int i=0;i<1;i++){
			TSPProblem tsp = new TSPProblem();
			M2M moead = new M2M(tsp, -1, i);
			moead.execute(1000);
		}
	}
}
